package 数组;

import java.util.Arrays;

/**
 * 移除元素
 *
 * 给你一个数组 num和一个值 val，你需要 原地 移除所有数值等于val的元素，并返回移除后数组的新长度。
 * 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
 * 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
 */

public class L27 {

    public static void main(String[] args) {

        int[] nums = {4,5};
//        int[] nums = {3,2,2,3};
//        int[] nums = {0,1,2,2,3,0,4,2};
        int len = removeElement(nums, 5);
        Arrays.stream(nums).forEach(System.out::print);
        for (int i = 0; i < len; i++) {
            System.out.println(nums[i]);
        }

    }

    // 双指针法进行替换（不够官方的优雅）
    public static int removeElement(int[] nums, int val) {

        if (nums.length == 0) {
            return 0;
        }

        int length = 0;
        int begin = 0;
        int last = nums.length - 1;
        while (begin < last) {


            if (nums[last] == val) last--;

            if (nums[begin] != val) {
                begin++;
                length++;
            }

            if (nums[begin] == val && nums[last] != val && begin <= last) {
                int temp = nums[begin];
                nums[begin] = nums[last];
                nums[last] = temp;
                begin++;
                last--;
                length++;
            }

        }
        if (nums[begin] != val) {
            length++;
        }

        return length;
    }


    /*
    官方答案（双指针）
    当 nums[j] 与给定的值相等时，递增 j 以跳过该元素。只要 nums[j]=val，
    我们就复制 nums[j] 到 nums[i] 并同时递增两个索引。重复这一过程，直到 j 到达数组的末尾，该数组的新长度为 i。
     */
    public int removeElement1(int[] nums, int val) {
        int i = 0;
        for (int j = 0; j < nums.length; j++) {
            if (nums[j] != val) {
                nums[i] = nums[j];
                i++;
            }
        }
        return i;
    }

    /*
    当我们遇到 nums[i]=val 时，我们可以将当前元素与最后一个元素进行交换，并释放最后一个元素。
    这实际上使数组的大小减少了 1。

    作者：LeetCode
    链接：https://leetcode-cn.com/problems/remove-element/solution/yi-chu-yuan-su-by-leetcode/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    public int removeElement2(int[] nums, int val) {
        int i = 0;
        int n = nums.length;
        while (i < n) {
            if (nums[i] == val) {
                nums[i] = nums[n - 1];
                // reduce array size by one
                n--;
            } else {
                i++;
            }
        }
        return n;
    }
}
